DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.23

Submodular Norms with Applications To Online Facility Location and Stochastic Probing

Authors: Kalen Patton, Matteo Russo, and Sahil Singla

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract

Optimization problems often involve vector norms, which has led to extensive research on developing algorithms that can handle objectives beyond 𝓁_p norms. Our work introduces the concept of submodular norms, which are a versatile type of norms that possess marginal properties similar to submodular set functions. We show that submodular norms can either accurately represent or approximate well-known classes of norms, such as 𝓁_p norms, ordered norms, and symmetric norms. Furthermore, we establish that submodular norms can be applied to optimization problems such as online facility location and stochastic probing. This allows us to develop a logarithmic-competitive algorithm for online facility location with symmetric norms, and to prove logarithmic adaptivity gap for stochastic probing with symmetric norms.

Cite as

Kalen Patton, Matteo Russo, and Sahil Singla. Submodular Norms with Applications To Online Facility Location and Stochastic Probing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{patton_et_al:LIPIcs.APPROX/RANDOM.2023.23,
  author =	{Patton, Kalen and Russo, Matteo and Singla, Sahil},
  title =	{{Submodular Norms with Applications To Online Facility Location and Stochastic Probing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.23},
  URN =		{urn:nbn:de:0030-drops-188484},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.23},
  annote =	{Keywords: Submodularity, Monotone Norms, Online Facility Location, Stochastic Probing}
}

Search Results

Documents authored by Russo, Matteo

Submodular Norms with Applications To Online Facility Location and Stochastic Probing

Abstract

Cite as

Thanks for your feedback!

Could not send message